//----------------------------------------------------------------------离散对数

//hash_table
//每次初始化:top=maxn;idx++;
const int maxn = 65535;
struct hash{
    int a,b,next;
}Hash[maxn << 1];
int flg[maxn + 66];
int top,idx;
void ins(int a,LL b){
    LL k = b & maxn;
    if(flg[k] != idx){
        flg[k] = idx;
        Hash[k].next = -1;
        Hash[k].a = a;
        Hash[k].b = b;
        return ;
    }
    while(Hash[k].next != -1){
        if(Hash[k].b == b) return ;
        k = Hash[k].next;
    }
    Hash[k].next = ++ top;
    Hash[top].next = -1;
    Hash[top].a = a;
    Hash[top].b = b;
}
int find(int b){
    int k = b & maxn;
    if(flg[k] != idx) return -1;
    while(k != -1){
        if(Hash[k].b == b) return Hash[k].a;
        k = Hash[k].next;
    }
    return -1;
}


//BABY-STEP GAINT=STEP   (扩展版,可算模数非素数的情况)
int inv(int a,int b)
{
    LL x,y;
    ext_gcd(a,b,x,y);
    return (int)((x%b+b)%b);
}
int babystep(int a,int c,int b)// a^x == b mod c
{
    top=maxn+1;idx++;//init hashtable
    LL D=1,tmp=1%c,d=0;
    for(int i=0;i<100;i++,tmp=tmp*a%c)if(tmp==b)return i;//小结果排除
    while((tmp=gcd(a,c))>1)
    {
        if(b%tmp)return -1;
        b/=tmp;
        d++;
        c/=tmp;
        D=D*a/tmp%c;
    }
    b=(int)(b*(LL)inv(D,c)%c);
    if(gcd(b,c)>1)return -1;

    int m=(int)ceil(sqrt(c));
    tmp=1%c;
    for(int i=0;i<=m;i++,tmp=tmp*a%c)ins(i,tmp);
    LL aa=inv(mod_exp(a,m,c),c);
    LL l=1;
    for(int i=0;i<=m;i++,l=aa*l%c)
    {
        int j=find(b*l%c);
        if(j>=0)return i*m+j+d;
    }
    return -1;
}
